package day3;

/**
 * 题目描述：
 * 
 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，
 * 其余每个元素都恰出现 三次 。请找出那个只出现了一次的元素。
 * 示例 1：输入：nums = [2,2,3,2] 输出：3 
 * 
 * 分析：
 * 将数字拆分为每一位，则重复出现三次的数字，对应位上的和对3求余数为0。
 * 因此对单个二进制位来看，会有三种状态0，1，2，这是一种有限状态自动机。
 * 对应的使用00，01，10二进制来表示三种状态。在这种情况下则需要利用到
 * 异或运算和与运算的二进制特性，
 * 对于任意二进制位x：x^0=x,x^1=～x
 *                 x&0=0,x&1=x
 * 使用a来表示三种状态的高位，b来表示三种状态的低位
 * 通过状态表拆分可以得出：
 * a=a^num&~b
 * b=b^num&~a
 * 因为两者等价关系，故获取相应位相同，通过该计算就可以获取到对应的数
 * 
 * 
 */
public class SingleNumber {

    public static int singleNumber(int[] array){
        if (array==null||array.length<2) {
            return array[0];
        }

        int oneBit=0;
        int twoBit=0;
        for (int i = 0; i < array.length; i++) {
            oneBit=oneBit^array[i]&~twoBit;
            twoBit=twoBit^array[i]&~oneBit;
        }
        return oneBit;
    }

    public static void main(String[] args) {
        int[] test=new int[]{2,2,7,5,5,2,5,9,3,9,9,3,3};
        System.out.println(singleNumber(test));
    }
    
}